[BAEKJOON] 4991. 로봇 청소기
Posted on
문제 :
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력 :
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
.: 깨끗한 칸: 더러운 칸x: 가구o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력 :
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
풀이 :
이 문제의 핵심은 BFS 탐색에서 방문 여부를 따지는 경우를 조금 변형해주어야 한다.
더러운 공간이 10개 이하이기 때문에 각 공간에 0~9 숫자를 부여하여 각 숫자를 방문하게 되면 해당 자릿수를 체크해주는 비트마스크 방식으로 2^10 크기의 20*20 배열을 만들어주어야 한다.
방문여부를 다음과 같이 설정해주게 되면 같은 칸을 여러번 방문하는 경우도 빠짐 없이 체크가 가능하다.
다만 조금 헷갈렸던 부분은 우선순위큐를 사용해야 문제가 해결되는 것인지였는데,
해당 큐는 이동 횟수대로 쌓여가기 때문에 굳이 우선순위를 구현해 줄 필요가 없었다. → 우선순위큐로 구현해도 문제는 없지만 시간복잡도가 늘어남.
코드 :
코드 보기/접기
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
typedef struct Node {
int x, y, cnt, dist;
};
int w, h, di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
char map[20][20];
bool visit[2050][20][20];
int bfs(int stx, int sty, int dirties) {
memset(visit, false, sizeof(visit));
queue<Node> q;
int destcnt = pow(2, dirties) - 1;
q.push(Node{stx, sty, 0, 0});
while (!q.empty()) {
int curx = q.front().x, cury = q.front().y, curcnt = q.front().cnt, curd = q.front().dist;
q.pop();
if (visit[curcnt][curx][cury]) continue;
if (curcnt == destcnt) return curd;
visit[curcnt][curx][cury] = true;
for (int k = 0; k < 4; k++) {
int cmpx = curx + di[k], cmpy = cury + dj[k], cmpcnt = curcnt;
if (cmpx < 0 || h <= cmpx || cmpy < 0 || w <= cmpy) continue;
if (map[cmpx][cmpy] == 'x') continue;
if (map[cmpx][cmpy] != '.') cmpcnt = cmpcnt | (1 << (map[cmpx][cmpy] - '0'));
if (!visit[cmpcnt][cmpx][cmpy]) q.push(Node{cmpx, cmpy, cmpcnt, curd + 1});
}
}
return -1;
}
int main() {
char input;
while (1) {
int cnt = 0, stx, sty;
cin >> w >> h;
if (!w && !h) break;
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++) {
cin >> input;
if (input == '*') map[i][j] = cnt++ + '0';
else if (input == 'o') {
stx = i;
sty = j;
map[i][j] = '.';
} else map[i][j] = input;
}
cout << bfs(stx, sty, cnt) << '\n';
}
return 0;
}